package buildTree;

import util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: javase
 * @description: 二叉树的序列化与反序列化
 * @author: luolidong
 * @create: 2021-06-25 16:47
 * @version: 1.0
 */
public class BuildTreeByString {
    /**
    * @Description: 通过树获取层次字符串，包含null
    * @Param: [root]
    * @return: java.lang.String
    */
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                sb.append(node.val);
                //如果不输出null,就判空
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                // 为空
                sb.append("null");
            }
            sb.append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    /**
     * 1
     * / \
     * 2   3
     * / \
     * 4  5
     * / \
     * 6   7
     */
    // 通过2*i+1获取子节点只适用于平衡二叉树
//    public TreeNode deserialize(String data) {
//        String[] s = data.split(",");
//        if (s[0].equals("null")) return null;
//        TreeNode[] treeNodes = new TreeNode[s.length];
//        for (int i = 0; i < s.length; i++) {
//            if (!s[i].equals("null")) {
//                treeNodes[i] = new TreeNode(Integer.parseInt(s[i]));
//            } else {
//                treeNodes[i] = null;
//            }
//        }
//        for (int i = 0; i < s.length; i++) {
//            if (treeNodes[i] != null && 2 * i + 1 < s.length) {
//                treeNodes[i].left = treeNodes[2 * i + 1];
//            }
//            if (treeNodes[i] != null && 2 * i + 2 < s.length) {
//                treeNodes[i].right = treeNodes[2 * i + 2];
//            }
//        }
//        return treeNodes[0];
//    }
    /**
    * @Description: 通过层次字符串构造树
    * @Param: [data]
    * @return: util.TreeNode
    */
    public TreeNode deserialize(String data) {
        if(data.equals("")) return null;
        String[] s = data.split(",");
        if (s[0].equals("null")) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode head = new TreeNode(Integer.parseInt(s[0]));
        queue.offer(head);

        for (int i = 1; i < s.length; i++) {
            TreeNode node = queue.poll();
            if (node == null) continue;
            if (!s[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(s[i]));
                queue.offer(node.left);
            }
            //i++代表右节点
            i++;
            if (!s[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(s[i]));
                queue.offer(node.right);
            }

        }
        return head;
    }

    public static void main(String[] args) {
        BuildTreeByString main = new BuildTreeByString();
        String serialize = main.serialize(TreeNode.build());
        System.out.println(serialize);

        TreeNode deserialize = main.deserialize(serialize);
        System.out.println("deserialize = " + deserialize);
        List<Integer> list=new ArrayList<>();
    }
}
